//
// Created by francklinson on 2021/6/22.
//

//实现获取 下一个排列 的函数，算法需要将给定数字序列重新排列成字典序中下一个更大的排列。
//
//如果不存在下一个更大的排列，则将数字重新排列成最小的排列（即升序排列）。
//
//必须 原地 修改，只允许使用额外常数空间。
//
//来源：力扣（LeetCode）
//链接：https://leetcode-cn.com/problems/next-permutation
//著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

#include <vector>
#include <iostream>
#include <algorithm>

using namespace std;

class Solution {
public:
    void nextPermutation(vector<int> &nums) {
        int i = nums.size() - 2;
        while (i >= 0 and nums[i] > nums[i + 1]) --i; // 从后往前遍历 找到下降点
        if (i >= 0) {
            int j = nums.size() - 1;
            while (j >= 0 and nums[j] <= nums[i]) --j; // 从后往前遍历，找到第一个比nums[i]大的数
            swap(nums[i], nums[j]); // 交换i j 位置的数字
        }
        reverse(nums.begin() + i + 1, nums.end()); // 将交换后i 右边的数变为升序排列
    }
};

int main() {
    vector<int> nums{1, 2, 3};
    Solution sol;
    sol.nextPermutation(nums);
//    next_permutation(nums.begin(),nums.end()); // stl内置函数 原理和上述的类似
    for (auto &x:nums) {
        cout << x << endl;
    }
    return 0;
}